// https://www.bilibili.com/video/BV1d54y1f7B3?spm_id_from=333.788.player.switch&vd_source=d6fe65f095f01f05591e89d810720ccc&p=33
// 2024-10-24

public class P036_字符串搜索_KMP算法 {

    public static void main(String[] args) {
        String txt = "ABCABCAABCABCD";
        String pat = "ABCABCD";

        System.out.println(KMP(txt,pat));
    }

    private static int KMP(String txt, String pat) {
        return KMP(txt.toCharArray(),pat.toCharArray(),getNext(pat.toCharArray()));
    }

    // KMP算法逻辑
    private static int KMP(char[] txt, char[] pat,int[] next) {
        int i = 0, j = 0;
        while (i < txt.length && j < pat.length) {
            if (j == -1 || txt[i] == pat[j]) {
                // 匹配上了，则后移
                i++;
                j++;
            }else {
                // 没匹配上
                j = next[j];
            }
        }

        if (j == pat.length) return i - j;
        return -1;
    }


    // 获取next数组
    private static int[] getNext(char[] pattern) {
        int[] next = new int[pattern.length];
        next[0] = -1;
        int i = 0, j = -1;//指向前缀或者后缀

        while (i < pattern.length) {
            if (j == -1) {
                i++;
                j++;
            }else if (pattern[i] == pattern[j]) {
                // 匹配上了
                i++;
                j++;
                next[i] = j;
            }else {
                // 没匹配上
                j = next[j];
            }
        }
        return next;
    }

}
